package com.springboot.demo.sort;

/**
 * 直接插入排序，稳定
 *
 * <p>
 * 算法思想：
 * <p>
 * 1、首先设定插入次数，即循环次数，for（int i=1；i < length；i++），1个数的那次不用插入
 * <p>
 * 2、设定插入数和已经得到排好序列的最后一位数的位置，即insertNum 和 j = i -1
 * <p>
 * 3、从最后一个数开始向前循环，如果插入数小于当前数，就将当前数向后移动一位
 * <p>
 * 4、将当前数放置到空着的位置，即 j+1
 *
 * 时间复杂度：o(n)~o(n^2)，平均是o(n^2)
 * 空间复杂度：o(1)
 *
 * @author supu
 * @date 2019-12-12 10:32
 **/
public class InsertSort {
    public static void insertSort(int[] a) {
        int length = a.length;
        // 要插入的数
        int insertNumber;
        // 插入次数
        for (int i = 1; i < length; i++) {
            // 要插入的数，从第二个数开始即可，因为第一个数不需要排序
            insertNumber = a[i];
            // 目前排好序的最大数的位置
            int j = i - 1;
            // 排好序数从后向前循环
            while (j >= 0 && a[j] > insertNumber) {
                // j 位置的数大于插入数，则 j 位置的数后移一位
                a[j + 1] = a[j];
                j--;
            }

            // 要插入的数放到 j+1 的位置处
            a[j + 1] = insertNumber;
        }
    }

    public static void insertSort1(int[] a){
        /*int length = a.length;
        int insertNum;
        for (int i = 1; i < length; i++) {
            insertNum = a[i];
            int j = i -1;
            while (j >= 0 && a[j] > insertNum){
                a[j+1] = a[j];
                j--;
            }
            a[j+1] = insertNum;
        }*/
        int length = a.length;
        int insertNum;
        for (int i = 1; i < length; i++) {
            insertNum = a[i];
            int j = i - 1;
            while (j >= 0 && a[j] > insertNum){
                a[j+1] = a[j];
                j--;
            }
            a[j+1] = insertNum;
        }
    }
}
